#include <iostream>
using namespace std;
#include <vector>
#include <cmath>

//只使用一趟遍历，势必要想办法找到当前数字和之前的数字有什么关系，这里我找的是前一个
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ret(n + 1, 0);
        //第一个位置的答案必然是0
        //然后我们知道的是，前一个位置就是当前位置的减1
        //减1的本质就是，以最右边一个1为分界线
        //左边不变，右边取反，原本最右边的1变成0！
        
        //i   [左边一样] 最右边的1 [右边全0]
        //i-1 [左边一样] 这个位置0 [右边全1]
        //i的1的个数 = (i-1)的1个数 - (y - 1) y为右边区间的长度
        for(int i = 1; i <= n; ++i){
            //右边长度怎么算？ -> 就是当前取出来对应的只有一个最右边1的数字，然后取以2为底对数即可！！！
            int len = i & (-i); //00010000..
            len = log(len) / log(2); //log的效率很高，基本为O(1)
            ret[i] = ret[i - 1] - len + 1;
        }
        return ret;
    }
};